#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include"linkstack.h"//导入栈
#include"../linkqueue/queue.h"//导入队列

int get_priority(char op);//运算符优先级

int main(int argc, char *argv[])
{
    if (argc < 2)
        return 1;

    stack_t *opstack = NULL;    // 运算符栈
    stack_t *result = NULL;     // 结果栈
    int i;// 控制大循环
    char c, temp;

    stack_init(&opstack, sizeof(char));//初始化运算符栈
    stack_init(&result, sizeof(char));//初始化结果栈

    // 从右向左扫描表达式！！！！why???
    i = strlen(argv[1]) - 1;
    while (i >= 0) {
        c = argv[1][i];
        if (c >= '1' && c <= '9') {
            // 操作数直接压入结果栈
            stack_push(result, &c);
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            // 处理运算符
            while (!stack_empty(opstack)) {
                stack_pop(opstack, &temp);
                if (get_priority(temp) > get_priority(c)){//栈里的优先级高  把运算符栈取出的  放入结果栈  ，循环结束把当前比较的放进去
                    stack_push(result, &temp);
                } else {
                    stack_push(opstack, &temp);// 栈里的优先级低，都放进运算符栈  循环结束把当前比较的放进去
                    break;
                }
            }
            stack_push(opstack, &c);
        }
        i--;
    }

    // 将剩余的运算符压入结果栈
    while (!stack_empty(opstack)) {
        stack_pop(opstack, &c);
        stack_push(result, &c);
    }

    // 输出前缀表达式
    printf("前缀表达式：");
    while (!stack_empty(result)) {
        stack_pop(result, &c);
        putchar(c);
    }
    putchar('\n');

    stack_destroy(&opstack);
    stack_destroy(&result);

    return 0;
}

int get_priority(char op)
{
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return -1;
    }
}
